Abstract: Cuckoo hashing is a method of creating and maintaining hash tables that has been widely used in both theory and practice. Random walk d-ary cuckoo hashing is a natural generalization of cuckoo hashing with low space overhead, guaranteed fast access, and fast in practice insertion time. In this presentation, I will explain random walk d-ary cuckoo hashing and my work giving a theoretical insertion time bound for this algorithm. More precisely, we show that for four or more hash functions and load factors up to the optimal threshold, the expectation of the random walk insertion time is O(1), that is, a constant depending only on the number of hash functions and the load factor, not the size of the table. This is joint work with Alan Frieze, see https://arxiv.org/abs/2401.14394.
Theory Lunch
O(1) Insertion for Random Walk d-ary Cuckoo Hashing
February 28, 2024 (GHC 8102)